﻿package org.dm.utils
{
	import org.dm.utils.Iterator;
	
	
	public class Map
	{	
		private var _nodes:Array = new Array;
		private var _len:int = 0;
		private var _compareFunc:Function = null;
		
		public function Map(func:Function = null)
		{
			_compareFunc = func;
		}
		
		public function get lenth():int
		{
			return _len; 
		}
		
		public function isEmpty():Boolean
		{
			return _len==0;
		}
		
		public function clear():void
		{
			for each (var item:Iterator in _nodes)
			{
				item.release();
				//delete item;
			}

			_nodes.length = 0;
			_len = 0;
		}
		
		public function get first():Iterator 
		{ 
			return _len>0?_nodes[0]:null;
		}
		
		public function get end():Iterator 
		{ 
			return null; 
		}
		
		public function get last():Iterator 
		{
			return _len>0?_nodes[_len-1]:null;
		}
		
		public function find(key:*):Iterator
		{
			if(_len==0)
			{
				return null;
			}

			var beg:int = 0;
			var end:int = _len-1;
			var mid:int = 0;
			var miditer:Iterator;
			
			if(_compareFunc!=null)
			{
				while(beg<=end)
				{
					mid = (beg+end)/2;
					miditer = _nodes[mid];
					
					switch(_compareFunc(miditer.key,key))
					{
						case 0:
							return miditer;
							break;
						case 1:
							end = mid - 1;
							break;
						case -1:
							beg = mid + 1;
							break;
					}
				}
			}
			else
			{
				var keyval:int = Utils.GetKey_Hash(key);
				var midkeyval:int;
				while(beg<=end)
				{
					mid = (beg+end)/2;
					miditer = _nodes[mid];
					midkeyval = Utils.GetKey_Hash(miditer.key);
					
					if(midkeyval==keyval)
					{
						return miditer;
					}
					
					if(midkeyval>keyval)
					{
						end = mid - 1;
					}
					else
					{
						beg = mid + 1;
					}
				}
			}
			return null;
		}

		public function insert(key:*,data:*):Boolean
		{
			var beg:int = 0;
			var end:int = _len-1;
			var mid:int = 0;
			var miditer:Iterator;
			
			if(_compareFunc!=null)
			{
				while(beg<=end)
				{
					mid = (beg+end)/2;
					miditer = _nodes[mid];
					
					switch(_compareFunc(miditer.key,key))
					{
						case 0:
							return false;
							break;
						case 1:
							end = mid - 1;
							break;
						case -1:
							beg = mid + 1;
							break;
					}
				}
			}
			else
			{
				var keyval:int = Utils.GetKey_Hash(key);
				var midkeyval:int;
				while(beg<=end)
				{
					mid = (beg+end)/2;
					miditer = _nodes[mid];
					midkeyval = Utils.GetKey_Hash(miditer.key);
					
					if(midkeyval==keyval)
					{
						return false;
					}
					
					if(midkeyval>keyval)
					{
						end = mid - 1;
					}
					else
					{
						beg = mid + 1;
					}
				}
			}
			
			var node:Iterator = new Iterator(data,key);
			if(_len>beg)
			{
				node.next = _nodes[beg] as Iterator;	
				_nodes.splice(beg,0,node);
			}
			else
			{
				node.prev = _nodes[_nodes.length-1] as Iterator;
				_nodes.push(node);
			}
			
			++_len;
			
			return true;
		}
		
		public function erase(iter:Iterator):Iterator
		{
			if(iter==null) return null;
			
			var i:int;
			for(i=0;i<_len;i++)
			{
				if(iter===_nodes[i])
				{
					iter.release();
					_nodes.splice(i,1);
					--_len;
					
					return _len==0?null:_len[i];
				}
			}
			
			return null;
		}
		
		public function setvalue(key:*,data:*):void
		{
			var iter:Iterator = find(key);
			if(iter==null)
			{
				insert(key,data);	
			}
			else
			{
				iter.data = data;
			}
		}
		
		public function remove(key:*):void
		{
			erase(find(key));
		}
	}
}